#define _CRT_SECURE_NO_WARNINGS 1
//希尔排序
void SherSort(int* a, int size)
{
	int gap = size / 2;
	while (gap > 1)
	{
		//预排序
		gap /= 2;
		int i = 0;
		int j = 0;
		for (j = 0; j < gap; j++)
		{
			for (i = j; i < size - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];

					}
					else
					{
						break;
					}
					end -= gap;
				}
				a[end + gap] = tmp;
			}
		}
	}
}

int main()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	SherSort(a,sizeof(a)/sizeof(int));
	int i = 0;
	for ( i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}